package com.easy.leetcode.dp;

import java.util.Arrays;

//63. 不同路径 II
public class UniquePathsWithObstacles63 {
    public int uniquePathsWithObstacles(int[][] obstacleGrid) {
        //dp[i][j] 表示到达i,j位置的不同路径条数
        int m = obstacleGrid.length;
        int n = obstacleGrid[0].length;
        //特殊值
        int index = Integer.MAX_VALUE;
        int tmp = obstacleGrid[0][0];
        for (int i = 0; i < m; i++) {
            //大于该索引的值，到达的路径条数为0
            if (i >= index) {
                obstacleGrid[i][0] = 0;
                continue;
            }
            //有障碍物
            if (obstacleGrid[i][0] == 1) {
                //记录索引
                index = i;
                obstacleGrid[i][0] = 0;
            } else {
                //否则到达该位置的路径条数为1
                obstacleGrid[i][0] = 1;
            }
        }
        index = Integer.MAX_VALUE;
        obstacleGrid[0][0] = tmp;
        for (int j = 0; j < n; j++) {
            //大于该索引的值，到达的路径条数为0
            if (j >= index) {
                obstacleGrid[0][j] = 0;
                continue;
            }
            //有障碍物
            if (obstacleGrid[0][j] == 1) {
                //记录索引
                index = j;
                obstacleGrid[0][j] = 0;
            } else {
                //否则到达该位置的路径条数为1
                obstacleGrid[0][j] = 1;
            }
        }
        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                if (obstacleGrid[i][j] == 1) {
                    obstacleGrid[i][j] = 0;
                } else {
                    obstacleGrid[i][j] = obstacleGrid[i - 1][j] + obstacleGrid[i][j - 1];
                }
            }
        }
        //print(obstacleGrid);
        return obstacleGrid[m - 1][n - 1];
    }

    public int uniquePathsWithObstacles1(int[][] obstacleGrid) {
        //dp[i][j] 表示到达i,j位置的不同路径条数
        int m = obstacleGrid.length;
        int n = obstacleGrid[0].length;
        int[][] steps = new int[m][n];
        for (int i = 0; i < m; i++) {
            if (obstacleGrid[i][0] == 1) {
                break;
            } else {
                steps[i][0] = 1;
            }
        }
        for (int i = 0; i < n; i++) {
            if (obstacleGrid[0][i] == 1) {
                break;
            } else {
                steps[0][i] = 1;
            }
        }
        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                steps[i][j]=obstacleGrid[i][j]==1?0:steps[i - 1][j] + steps[i][j - 1];
            }
        }
        //print(steps);
        return steps[m-1][n-1];
    }


    public void print(int[][] obstacleGrid) {
        for (int i = 0; i < obstacleGrid.length; i++) {
            System.out.println(Arrays.toString(obstacleGrid[i]));
        }
    }
}
